package com.algorithm.base.backtracking;

import java.util.*;

/**
 * 组合总和
 *
 * @author Amadeus
 * @date 2023/11/02
 */
public class CombinationSum {

    /**
     * 组合总和
     *
     * @param candidates 候选人
     * @param target     目标
     * @return {@link List}<{@link List}<{@link Integer}>>
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Deque<Integer> deque = new ArrayDeque<>();
        Arrays.sort(candidates);
        backTrackingPruning(target, candidates, result, deque, 0);
        return result;
    }

    /**
     * 回溯
     *
     * @param target     目标
     * @param sum        总金额
     * @param result     结果
     * @param candidates 候选人
     */
    public void backTracking(int target, int sum, int[] candidates, List<List<Integer>> result, Deque<Integer> deque, int index) {
        if (sum == target) {
            result.add(new ArrayList<>(deque));
            return;
        }
        if (sum > target) {
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            sum += candidates[i];
            deque.addLast(candidates[i]);
            backTracking(target, sum, candidates, result, deque, i);
            sum -= candidates[i];
            deque.removeLast();
        }
    }

    /**
     * 回溯剪枝
     *
     * @param target     目标
     * @param candidates 候选人
     * @param result     结果
     * @param deque      deque
     * @param index      索引
     */
    public void backTrackingPruning(int target, int[] candidates, List<List<Integer>> result, Deque<Integer> deque, int index) {
        if (0 == target) {
            result.add(new ArrayList<>(deque));
            return;
        }
        if (0 > target) {
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            if (target < candidates[i]) {
                break;
            }
            target -= candidates[i];
            deque.addLast(candidates[i]);
            backTrackingPruning(target, candidates, result, deque, i);
            target += candidates[i];
            deque.removeLast();
        }
    }

}
